package com.jia.leetCode;

import java.util.*;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-17 02:07
 */
public class Pro0127 {
    //bfs
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        Set<String> set = new HashSet<>();
        if(beginWord.equals(endWord) || !wordList.contains(endWord)) return 0;
        set.add(beginWord);
        int ans = 1;
        for(queue.offer(beginWord), set.add(beginWord);!queue.isEmpty();) {
            int size = queue.size();
            ++ans;
            while(size-- > 0) {
                String str = queue.poll();
                StringBuilder sb = new StringBuilder(str);
                for(int i = 0; i < wordList.size(); i++) {
                    if(!set.contains(wordList.get(i))) {
                        if(isValid(str, wordList.get(i))) {
                            if(endWord.equals(wordList.get(i)) || str.length() == 1) {
                                return ans;
                            }
                            queue.add(wordList.get(i));
                            set.add(wordList.get(i));
                        }
                    }
                }

            }
        }
        return 0;
    }
    private boolean isValid(String str1, String str2) {
        int count = 0;
        for(int i = 0; i < str1.length(); i++) {
            if(str1.charAt(i) != str2.charAt(i)) ++count;
        }
        return count == 1;
    }

    public static void main(String[] args) {
        Pro0127 pro0127 = new Pro0127();
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Arrays.asList(new String[]{"hot","dot","dog","lot","log","cog"});
//        List<String> wordList = Arrays.asList(new String[]{"hot","dot","dog","lot","log"});
        System.out.println(pro0127.ladderLength(beginWord, endWord, wordList));
    }
}

